/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: LIUYANJIAO
 * Date: 2025-03-12
 * Time: 20:57
 */
public class Demo2 {

        public boolean exist(String[] board, String word) {
            if (board == null || board.length == 0) {
                return false;
            }
            int m = board.length;
            int n = board[0].length();
            boolean[][] visited = new boolean[m][n];

            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (board[i].charAt(j) == word.charAt(0)) {
                        visited[i][j] = true;
                        if (dfs(board, word, 1, i, j, visited)) {
                            return true;
                        }
                        visited[i][j] = false;
                    }
                }
            }
            return false;
        }

        private boolean dfs(String[] board, String word, int index, int i, int j, boolean[][] visited) {
            if (index == word.length()) {
                return true;
            }
            int m = board.length;
            int n = board[0].length();

            int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
            for (int[] dir : directions) {
                int newI = i + dir[0];
                int newJ = j + dir[1];
                if (newI >= 0 && newI < m && newJ >= 0 && newJ < n &&
                        !visited[newI][newJ] && board[newI].charAt(newJ) == word.charAt(index)) {
                    visited[newI][newJ] = true;
                    if (dfs(board, word, index + 1, newI, newJ, visited)) {
                        return true;
                    }
                    visited[newI][newJ] = false;
                }
            }
            return false;
        }

        public static void main(String[] args) {
            WordSearch ws = new WordSearch();
            String[] board = {"XYZE", "SFZS", "XDEE"};
            String word1 = "XYZZED";
            String word2 = "SEE";
            String word3 = "XYZY";

            System.out.println(ws.exist(board, word1));
            System.out.println(ws.exist(board, word2));
            System.out.println(ws.exist(board, word3));
        }

}
